/**
 * 
 */
package com.goldentrail.dml;

import java.util.ArrayList;
import java.util.Hashtable;
import java.util.Map.Entry;

import com.goldentrail.dataobject.DataArtifact;
import com.goldentrail.dataobject.Invocation;
import com.goldentrail.dataobject.Node;
import com.goldentrail.dataobject.Run;
import com.goldentrail.neo4j.Neo4jNode;
import com.goldentrail.neo4j.PathResult;
import com.goldentrail.neo4j.PathSpec;
import com.goldentrail.neo4j.Relationship;
import com.goldentrail.neo4j.TraverserSpec;
import com.goldentrail.neo4j.RelationshipSpec;

/**
 * Contains static methods for querying a Neo4j database containing runs
 * 
 * @author mikeagun
 * 
 */
public class Neo4jQuery {
	private static final int MAX_DEPTH = 1000000;

	/**
	 * Gets the ids of each run stored in the database
	 * 
	 * @return list of run ids
	 */
	public static ArrayList<String> getRunIds() {
		ArrayList<String> runs = new ArrayList<String>();
		Neo4jNode root = Neo4jNode.getNode(0);
		for (Relationship rel : root.getRelationships("in",
				Neo4jBuilder.ROOT_RUN_REL)) {
			runs.add(rel.getStartNode().getProperty("id"));
		}
		return runs;
	}

	/**
	 * Gets the ids of each invocation stored in the database
	 * 
	 * @return list of invocation ids
	 */
	public static ArrayList<String> getInvocIds() {
		ArrayList<String> invocs = new ArrayList<String>();
		Neo4jNode root = Neo4jNode.getNode(0);
		TraverserSpec t = new TraverserSpec();
		t.setOrder(TraverserSpec.DEPTH_FIRST);
		// t.setPruneEvaluator(TraverserSpec.JAVASCRIPT_LANG,
		// "position.endNode().getProperty('type')=='invoc'");
		t.setReturnFilterLanguage(TraverserSpec.JAVASCRIPT_LANG);
		t.setReturnFilterBody("position.endNode().hasProperty('type')&&position.endNode().getProperty('type')=='invoc'");
		t.setUniqueness(TraverserSpec.NODE_PATH_UNIQUENESS);
		ArrayList<RelationshipSpec> relations = new ArrayList<RelationshipSpec>();
		relations.add(new RelationshipSpec(Neo4jBuilder.ROOT_RUN_REL, "in"));
		relations.add(new RelationshipSpec(Neo4jBuilder.RUN_INVOC_REL, "in"));
		t.setRelationships(relations);
		t.setMaxDepth(2);
		ArrayList<Neo4jNode> invocNodes = root.traverseNode(t);
		for (Neo4jNode invocNode : invocNodes) {
			invocs.add(invocNode.getProperty("id"));
		}
		return invocs;
	}

	/**
	 * Gets the ids of each invocation in the specified run
	 * 
	 * @return list of invocation ids
	 */
	public static ArrayList<String> getInvocIds(String runId) {
		ArrayList<String> invocs = new ArrayList<String>();
		Neo4jNode run = Neo4jNode.getNode("run", "id", runId);
		if (run == null)
			return null;
		TraverserSpec t = new TraverserSpec();
		t.setOrder(TraverserSpec.DEPTH_FIRST);
		// t.setPruneEvaluator(TraverserSpec.JAVASCRIPT_LANG,
		// "position.endNode().getProperty('type')=='invoc'");
		t.setReturnFilterLanguage(TraverserSpec.JAVASCRIPT_LANG);
		t.setReturnFilterBody("position.endNode().getProperty('type')=='invoc'");
		t.setUniqueness(TraverserSpec.NODE_PATH_UNIQUENESS);
		ArrayList<RelationshipSpec> relations = new ArrayList<RelationshipSpec>();
		// relations.add(new RelationshipSpec(Neo4jBuilder.ROOT_RUN_REL, "in"));
		relations.add(new RelationshipSpec(Neo4jBuilder.RUN_INVOC_REL, "in"));
		t.setRelationships(relations);
		t.setMaxDepth(1);
		ArrayList<Neo4jNode> invocNodes = run.traverseNode(t);
		for (Neo4jNode invocNode : invocNodes) {
			invocs.add(invocNode.getProperty("id"));
		}
		return invocs;
	}

	/**
	 * Gets the ids of each data artifact stored in the database
	 * 
	 * @return list of data artifact ids
	 */
	public static ArrayList<String> getDataArtifactIds() {
		ArrayList<String> invocs = new ArrayList<String>();
		Neo4jNode root = Neo4jNode.getNode(0);
		TraverserSpec t = new TraverserSpec();
		t.setOrder(TraverserSpec.DEPTH_FIRST);
		// t.setPruneEvaluator(TraverserSpec.JAVASCRIPT_LANG,
		// "position.endNode().getProperty('type')=='data'");
		t.setReturnFilterLanguage(TraverserSpec.JAVASCRIPT_LANG);
		t.setReturnFilterBody("position.endNode().hasProperty('type')&&position.endNode().getProperty('type')=='data'");
		t.setUniqueness(TraverserSpec.NODE_GLOBAL_UNIQUENESS);
		ArrayList<RelationshipSpec> relations = new ArrayList<RelationshipSpec>();
		relations.add(new RelationshipSpec(Neo4jBuilder.ROOT_RUN_REL, "in"));
		relations.add(new RelationshipSpec(Neo4jBuilder.RUN_DATA_REL, "in"));
		t.setRelationships(relations);
		t.setMaxDepth(2);
		ArrayList<Neo4jNode> invocNodes = root.traverseNode(t);
		for (Neo4jNode invocNode : invocNodes) {
			invocs.add(invocNode.getProperty("id"));
		}
		return invocs;
	}

	/**
	 * Gets the ids of each data artifact in the specified run
	 * 
	 * @return list of data artifact ids
	 */
	public static ArrayList<String> getDataArtifactIds(String runId) {
		ArrayList<String> invocs = new ArrayList<String>();
		Neo4jNode run = Neo4jNode.getNode("run", "id", runId);
		if (run == null)
			return null;
		TraverserSpec t = new TraverserSpec();
		t.setOrder(TraverserSpec.DEPTH_FIRST);
		// t.setPruneEvaluator(TraverserSpec.JAVASCRIPT_LANG,
		// "position.endNode().getProperty('type')=='data'");
		t.setReturnFilterLanguage(TraverserSpec.JAVASCRIPT_LANG);
		t.setReturnFilterBody("position.endNode().getProperty('type')=='data'");
		t.setUniqueness(TraverserSpec.NODE_GLOBAL_UNIQUENESS);
		ArrayList<RelationshipSpec> relations = new ArrayList<RelationshipSpec>();
		// relations.add(new RelationshipSpec(Neo4jBuilder.ROOT_RUN_REL, "in"));
		relations.add(new RelationshipSpec(Neo4jBuilder.RUN_DATA_REL, "in"));
		t.setRelationships(relations);
		t.setMaxDepth(1);
		ArrayList<Neo4jNode> invocNodes = run.traverseNode(t);
		for (Neo4jNode invocNode : invocNodes) {
			invocs.add(invocNode.getProperty("id"));
		}
		return invocs;
	}

	/**
	 * Gets a run from the database using its runId. reconstructs the run as a
	 * com.goldentrail.dataobject.Run object with all its nodes.
	 * 
	 * @param runId
	 *            id of the run to reconstruct
	 * @return reconstructed Run from the database
	 */
	public static Run getRun(String runId) {
		Neo4jNode dbRun = getRunNode(runId);
		if (dbRun == null)
			return null;
		ArrayList<Invocation> invocs = new ArrayList<Invocation>();
		for (Relationship runInvocRel : dbRun.getRelationships("in",
				Neo4jBuilder.RUN_INVOC_REL)) {
			invocs.add(getInvocation(runInvocRel.getStartNode()));
		}
		Run r = Run.fromJSON(dbRun.getPropertiesJSON());
		r.setNodeUri(dbRun.getURI().toString());
		r.setInvocations(invocs);
		return r;
	}

	/**
	 * Gets the DataArtifact representation of the specified database node
	 * 
	 * @param dbData
	 *            Neo4jNode to build data artifact from
	 * @return data artifact built from specified node
	 */
	private static DataArtifact getDataArtifact(Neo4jNode dbData) {
		if (dbData == null)
			return null;
		if (!dbData.getProperty("type").equals("data"))
			return null;
		DataArtifact data = DataArtifact.fromJSON(dbData.getPropertiesJSON());
		data.setNodeUri(dbData.getURI().toString());
		return data;
	}

	/**
	 * Gets the Invocation representation of the specified database node.
	 * Includes all input and output data (as DataArtifacts)
	 * 
	 * @param dbData
	 *            Neo4jNode to build invocation from
	 * @return invocation built from specified node
	 */
	private static Invocation getInvocation(Neo4jNode dbInvoc) {
		if (dbInvoc == null)
			return null;
		Invocation invoc = Invocation.fromJSON(dbInvoc.getPropertiesJSON());
		invoc.setNodeUri(dbInvoc.getURI().toString());
		Hashtable<String, DataArtifact> in = new Hashtable<String, DataArtifact>();
		Hashtable<String, DataArtifact> out = new Hashtable<String, DataArtifact>();

		for (Relationship rel : dbInvoc.getRelationships("out",
				Neo4jBuilder.USED_REL)) {
			DataArtifact data = getDataArtifact(rel.getEndNode());
			in.put(data.getDataArtifactId(), data);
		}

		for (Relationship rel : dbInvoc.getRelationships("in",
				Neo4jBuilder.GEN_BY_REL)) {
			DataArtifact data = getDataArtifact(rel.getStartNode());
			out.put(data.getDataArtifactId(), data);
		}

		invoc.setInputData(in);
		invoc.setOutputData(out);

		return invoc;

	}

	/**
	 * Gets an invocation from the db without getting inputs/outputs. Used in
	 * path finding to get the bare info, then fill out as needed
	 * 
	 * @param dbInvoc
	 *            the db node to get the info from
	 * @return Invocation with only Uri, id, and type
	 */
	private static Invocation getInvocationNoData(Neo4jNode dbInvoc) {
		if (dbInvoc == null)
			return null;
		Invocation invoc = Invocation.fromJSON(dbInvoc.getPropertiesJSON());
		invoc.setNodeUri(dbInvoc.getURI().toString());

		return invoc;
	}

	/**
	 * puts run information for a run from the db into an Invocation object.
	 * Contains id,type, final outputs, and initial inputs
	 * 
	 * @param dbRun
	 *            The node to retrieve run info from
	 * @return Invocation representing run
	 */
	private static Invocation getRunAsInvoc(Neo4jNode dbRun) {
		if (dbRun == null)
			return null;
		Invocation invoc = Invocation.fromJSON(dbRun.getPropertiesJSON());
		invoc.setNodeUri(dbRun.getURI().toString());
		Hashtable<String, DataArtifact> in = new Hashtable<String, DataArtifact>();
		Hashtable<String, DataArtifact> out = new Hashtable<String, DataArtifact>();

		for (Relationship rel : dbRun.getRelationships("out",
				Neo4jBuilder.INIT_INPUT_REL)) {
			DataArtifact data = getDataArtifact(rel.getEndNode());
			in.put(data.getDataArtifactId(), data);
		}

		for (Relationship rel : dbRun.getRelationships("out",
				Neo4jBuilder.FINAL_OUTPUT_REL)) {
			DataArtifact data = getDataArtifact(rel.getStartNode());
			out.put(data.getDataArtifactId(), data);
		}

		invoc.setInputData(in);
		invoc.setOutputData(out);

		return invoc;
	}

	/**
	 * Finds all nodes that the depend on the given nodes, optionally limiting
	 * results to paths that pass through the specified nodes
	 * 
	 * @param endNodes
	 *            Nodes to start right facing traversal from
	 * @param throughNodes
	 *            nodes that all returned nodes must be on a path with. null to
	 *            not limit results
	 * @param runId
	 *            runId to limit results to. null to not limit results
	 * @return list of invocations containing only inputs/outputs on the
	 *         returned paths
	 */
	public static ArrayList<Invocation> getDependents(ArrayList<Node> endNodes,
			ArrayList<Node> throughNodes, String runId) {
		ArrayList<Invocation> results = new ArrayList<Invocation>();

		TraverserSpec t = new TraverserSpec();
		ArrayList<RelationshipSpec> relationships = new ArrayList<RelationshipSpec>();
		relationships.add(new RelationshipSpec(Neo4jBuilder.GEN_BY_REL, "in"));
		relationships.add(new RelationshipSpec(Neo4jBuilder.USED_REL, "in"));
		relationships.add(new RelationshipSpec(Neo4jBuilder.FINAL_OUTPUT_REL,
				"out"));
		t.setRelationships(relationships);
		t.setOrder(TraverserSpec.DEPTH_FIRST);
		t.setMaxDepth(MAX_DEPTH);
		/*
		 * t.setPruneEvaluator(Traverser.JAVASCRIPT_LANG,
		 * "!(position.endNode().hasRelationship('GEN_BY')||" +
		 * "postion.endNode().hasRelationship('USED'))");
		 */
		t.setUniqueness(TraverserSpec.NODE_PATH_UNIQUENESS);
		t.setReturnFilterLanguage(TraverserSpec.JAVASCRIPT_LANG);
		// t.setReturnFilterLanguage(Traverser.BUILTIN_LANG);
		// t.setReturnFilterName(Traverser.ALL_RETURN_FILTER);

		for (Node endNode : endNodes) {

			Neo4jNode neoEndNode = Neo4jNode.getNode(endNode.getNodeTp(), "id",
					endNode.getNodeId());
			if (neoEndNode == null)
				return null;
			String returnFilter = null;

			if (throughNodes != null) {
				returnFilter = "(function eval(pos) {";
				if (runId != null) {
					returnFilter += "var nodeIt = pos.nodes().iterator();"
							+ "var node = null;" + "while(nodeIt.hasNext()) {"
							+ "node = nodeIt.next();"
							+ "if (node.hasProperty('run'))"
							+ "if (node.getProperty('run')!='" + runId + "')"
							+ "return false;" + "}";
					t.setPruneEvaluator(
							TraverserSpec.JAVASCRIPT_LANG,
							"position.endNode().hasProperty('run')&&"
									+ "position.endNode().getProperty('run')!='"
									+ runId + "'");
				}
				returnFilter += "var throughNodes = "
						+ throughNodes.toString()
						+ ";"
						+ "var i = "
						+ throughNodes.size()
						+ ";"
						+
						// check each through node
						"while(i--) {" + "var hasThroughNode=false;"
						+ "var throughNode = throughNodes[i];"
						+ "var nodeIt = pos.nodes().iterator();"
						+ "var node = null;" + "while(nodeIt.hasNext()) {"
						+ "node = nodeIt.next();"
						+ "if(node.getProperty('type')==throughNode.type) {"
						+ "if(node.getProperty('id')==throughNode.id) {"
						+ "hasThroughNode=true;" + "break;" + "}" + "}" + "}"
						+ "if (!hasThroughNode)" + "return false;" + "}"
						+ "return true;" + "})(position)";
				t.setReturnFilterBody(returnFilter);
			} else {
				if (runId == null)
					t.setReturnFilter(TraverserSpec.ALL_RETURN_FILTER,
							TraverserSpec.BUILTIN_LANG, null);
				else {
					returnFilter = "(function eval(pos) {"
							+ "var nodeIt = pos.nodes().iterator();"
							+ "var node = null;" + "while(nodeIt.hasNext()) {"
							+ "node = nodeIt.next();"
							+ "if (node.hasProperty('run'))"
							+ "if (node.getProperty('run')!='" + runId + "')"
							+ "return false;" + "}" + "return true;"
							+ "})(position)";
					t.setPruneEvaluator(
							TraverserSpec.JAVASCRIPT_LANG,
							"position.endNode().hasProperty('run')&&"
									+ "position.endNode().getProperty('run')!='"
									+ runId + "'");
					t.setReturnFilterBody(returnFilter);
				}

			}
			ArrayList<PathResult> paths = neoEndNode.traversePath(t);
			for (PathResult path : paths) {
				int pathLength = path.getNodes().size();
				for (int i = 0; i < pathLength; i++) {
					Neo4jNode neoNode = path.getNodes().get(i);
					if (neoNode.getProperty("type").equals(
							Neo4jBuilder.INVOC_TYP)) {
						addInvoc(
								results,
								neoNode,
								((i < (pathLength - 1) ? path.getNodes().get(
										i + 1) : null)), (i > 0 ? path
										.getNodes().get(i - 1) : null));
					}
				}
			}
		}
		return results;
	}

	/**
	 * Finds all nodes that the given nodes depend on, optionally limiting
	 * results to paths that pass through the specified nodes
	 * 
	 * @param startNodes
	 *            Nodes to start left facing traversal from
	 * @param throughNodes
	 *            nodes that all returned nodes must be on a path with. null to
	 *            not limit results
	 * @param runId
	 *            runId to limit results to. null to not limit results
	 * @return list of invocations containing only inputs/outputs on the
	 *         returned paths
	 */
	public static ArrayList<Invocation> getDependencies(
			ArrayList<Node> startNodes, ArrayList<Node> throughNodes,
			String runId) {
		ArrayList<Invocation> results = new ArrayList<Invocation>();

		TraverserSpec t = new TraverserSpec();
		ArrayList<RelationshipSpec> relationships = new ArrayList<RelationshipSpec>();
		relationships.add(new RelationshipSpec(Neo4jBuilder.GEN_BY_REL, "out"));
		relationships.add(new RelationshipSpec(Neo4jBuilder.USED_REL, "out"));
		relationships.add(new RelationshipSpec(Neo4jBuilder.INIT_INPUT_REL,
				"out"));
		t.setRelationships(relationships);
		t.setOrder(TraverserSpec.DEPTH_FIRST);
		t.setMaxDepth(MAX_DEPTH);
		/*
		 * t.setPruneEvaluator(Traverser.JAVASCRIPT_LANG,
		 * "!(position.endNode().hasRelationship('GEN_BY')||" +
		 * "postion.endNode().hasRelationship('USED'))");
		 */
		t.setUniqueness(TraverserSpec.NODE_PATH_UNIQUENESS);
		t.setReturnFilterLanguage(TraverserSpec.JAVASCRIPT_LANG);
		// t.setReturnFilterLanguage(Traverser.BUILTIN_LANG);
		// t.setReturnFilterName(Traverser.ALL_RETURN_FILTER);

		for (Node startNode : startNodes) {

			Neo4jNode neoStartNode = Neo4jNode.getNode(startNode.getNodeTp(),
					"id", startNode.getNodeId());
			if (neoStartNode == null)
				return null;
			String returnFilter = null;

			if (throughNodes != null) {
				returnFilter = "(function eval(pos) {";
				if (runId != null) {
					returnFilter += "var nodeIt = pos.nodes().iterator();"
							+ "var node = null;" + "while(nodeIt.hasNext()) {"
							+ "node = nodeIt.next();"
							+ "if (node.hasProperty('run'))"
							+ "if (node.getProperty('run')!='" + runId + "')"
							+ "return false;" + "}";
					t.setPruneEvaluator(
							TraverserSpec.JAVASCRIPT_LANG,
							"position.endNode().hasProperty('run')&&"
									+ "position.endNode().getProperty('run')!='"
									+ runId + "'");
				}
				returnFilter += "var throughNodes = "
						+ throughNodes.toString()
						+ ";"
						+ "var i = "
						+ throughNodes.size()
						+ ";"
						+
						// check each through node
						"while(i--) {" + "var hasThroughNode=false;"
						+ "var throughNode = throughNodes[i];"
						+ "var nodeIt = pos.nodes().iterator();"
						+ "var node = null;" + "while(nodeIt.hasNext()) {"
						+ "node = nodeIt.next();"
						+ "if(node.getProperty('type')==throughNode.type) {"
						+ "if(node.getProperty('id')==throughNode.id) {"
						+ "hasThroughNode=true;" + "break;" + "}" + "}" + "}"
						+ "if (!hasThroughNode)" + "return false;" + "}"
						+ "return true;" + "})(position)";
				t.setReturnFilterBody(returnFilter);
			} else {
				if (runId == null)
					t.setReturnFilter(TraverserSpec.ALL_RETURN_FILTER,
							TraverserSpec.BUILTIN_LANG, null);
				else {
					returnFilter = "(function eval(pos) {"
							+ "var nodeIt = pos.nodes().iterator();"
							+ "var node = null;" + "while(nodeIt.hasNext()) {"
							+ "node = nodeIt.next();"
							+ "if (node.hasProperty('run'))"
							+ "if (node.getProperty('run')!='" + runId + "')"
							+ "return false;" + "}" + "return true;"
							+ "})(position)";
					t.setPruneEvaluator(
							TraverserSpec.JAVASCRIPT_LANG,
							"position.endNode().hasProperty('run')&&"
									+ "position.endNode().getProperty('run')!='"
									+ runId + "'");
					t.setReturnFilterBody(returnFilter);
				}

			}
			ArrayList<PathResult> paths = neoStartNode.traversePath(t);
			for (PathResult path : paths) {
				int pathLength = path.getNodes().size();
				for (int i = 0; i < pathLength; i++) {
					Neo4jNode neoNode = path.getNodes().get(i);
					if (neoNode.getProperty("type").equals(
							Neo4jBuilder.INVOC_TYP)) {
						addInvoc(
								results,
								neoNode,
								(i > 0 ? path.getNodes().get(i - 1) : null),
								((i < (pathLength - 1) ? path.getNodes().get(
										i + 1) : null)));
					}
				}
			}
		}
		return results;
	}

	/**
	 * Find all paths between two nodes. If there are multiple nodes with the
	 * same id/type, find paths between all of them
	 * 
	 * @param startNode
	 *            The node to start from (the rightmost node)
	 * @param endNode
	 *            The node to end at (leftmost node)
	 * @return null if a given node doesn't exist, else all invocations in the
	 *         paths
	 */
	public static ArrayList<Invocation> getPaths(Node startNode, Node endNode) {
		// I'm dealing with Neo4jNodes until the very end because it's easier to
		// check whether two Invocations are the same node
		ArrayList<Invocation> results = new ArrayList<Invocation>();

		ArrayList<Neo4jNode> node1list = Neo4jNode.getNodes(
				startNode.getNodeTp(), "id", startNode.getNodeId());
		ArrayList<Neo4jNode> node2list = Neo4jNode.getNodes(
				endNode.getNodeTp(), "id", endNode.getNodeId());
		if (node1list == null || node2list == null)
			return null;
		if (node1list.size() < 1 || node2list.size() < 1)
			return null;

		ArrayList<RelationshipSpec> relationships = new ArrayList<RelationshipSpec>();
		relationships.add(new RelationshipSpec(Neo4jBuilder.GEN_BY_REL, "out"));
		relationships.add(new RelationshipSpec(Neo4jBuilder.USED_REL, "out"));
		relationships.add(new RelationshipSpec(Neo4jBuilder.INIT_INPUT_REL,
				"out"));

		// go through each pairing of start and end nodes
		for (Neo4jNode node1 : node1list) {
			for (Neo4jNode node2 : node2list) {
				PathSpec spec = new PathSpec();
				spec.setAlgorithm(PathSpec.ALL_PATHS); // find all paths between
														// the nodes
				spec.setMaxDepth(MAX_DEPTH);
				spec.setToNode(node2);
				spec.setRelationships(relationships);
				// find the paths
				ArrayList<PathResult> paths = node1.findPaths(spec);

				for (PathResult path : paths) {
					int pathLength = path.getNodes().size();
					for (int i = 0; i < pathLength; i++) {
						Neo4jNode neoNode = path.getNodes().get(i);
						if (neoNode.getProperty("type").equals(
								Neo4jBuilder.INVOC_TYP)) {
							addInvoc(results, neoNode, (i > 0 ? path.getNodes()
									.get(i - 1) : null),
									((i < (pathLength - 1) ? path.getNodes()
											.get(i + 1) : null)));
						}
					}
				}
			}
		}

		return results;
	}

	/**
	 * Find all paths between pairs of nodes. If there are multiple nodes with
	 * the same id within a pair, find paths between all of them. Finds all
	 * paths from each key node to each of the nodes in its value list
	 * 
	 * @param nodePairs
	 *            Hashtable containing all the pairs of nodes (keys are start
	 *            nodes, i.e. rightmost nodes)
	 * @return null if a node doesn't exist, else all invocations in the paths
	 */
	public static ArrayList<Invocation> getPaths(
			Hashtable<Node, ArrayList<Node>> nodePairs) {
		// I'm dealing with Neo4jNodes until the very end because it's easier to
		// check whether two Invocations are the same node (just check URL)
		//
		// This is also why I don't simply call the simple getPaths(Node,Node)
		// on every pair in the foreach loop

		ArrayList<Invocation> results = new ArrayList<Invocation>();

		ArrayList<RelationshipSpec> relationships = new ArrayList<RelationshipSpec>();
		relationships.add(new RelationshipSpec(Neo4jBuilder.GEN_BY_REL, "out"));
		relationships.add(new RelationshipSpec(Neo4jBuilder.USED_REL, "out"));
		relationships.add(new RelationshipSpec(Neo4jBuilder.INIT_INPUT_REL,
				"out"));

		for (Entry<Node, ArrayList<Node>> nodePair : nodePairs.entrySet()) {
			ArrayList<Neo4jNode> node1list = Neo4jNode.getNodes(nodePair
					.getKey().getNodeTp(), "id", nodePair.getKey().getNodeId());
			if (node1list == null)
				return null;
			if (node1list.size() < 1)
				return null;

			for (Node endNode : nodePair.getValue()) {
				ArrayList<Neo4jNode> node2list = Neo4jNode.getNodes(
						endNode.getNodeTp(), "id", endNode.getNodeId());
				if (node1list == null || node2list == null)
					return null;
				if (node1list.size() < 1 || node2list.size() < 1)
					return null;

				// go through each pairing of start and end nodes
				for (Neo4jNode node1 : node1list) {
					for (Neo4jNode node2 : node2list) {
						PathSpec spec = new PathSpec();
						spec.setAlgorithm(PathSpec.ALL_PATHS); // find all paths
																// between the
																// nodes
						spec.setMaxDepth(MAX_DEPTH);
						spec.setToNode(node2);
						spec.setRelationships(relationships);
						// find the paths
						ArrayList<PathResult> paths = node1.findPaths(spec);

						for (PathResult path : paths) {
							int pathLength = path.getNodes().size();
							for (int i = 0; i < pathLength; i++) {
								Neo4jNode neoNode = path.getNodes().get(i);
								if (neoNode.getProperty("type").equals(
										Neo4jBuilder.INVOC_TYP)) {
									addInvoc(results, neoNode, (i > 0 ? path
											.getNodes().get(i - 1) : null),
											((i < (pathLength - 1) ? path
													.getNodes().get(i + 1)
													: null)));
								}
							}
						}
					}
				}
			}
		}

		return results;
	}

	/**
	 * Find all paths between pairs of nodes. If there are multiple nodes with
	 * the same id within a pair, find paths between all of them, only include
	 * nodes that are within the specified run
	 * 
	 * @param nodePairs
	 *            Hashtable containing all the pairs of nodes (keys are start
	 *            nodes)
	 * @param throughNodes
	 *            nodes that all returned paths must pass through. null to not
	 *            limit results
	 * @param runId
	 *            The id of the run to limit results to. null to not limit
	 *            results
	 * @return null if a node doesn't exist, else all invocations in the paths
	 */
	public static ArrayList<Invocation> getPaths(
			Hashtable<Node, ArrayList<Node>> nodePairs,
			ArrayList<Node> throughNodes, String runId) {
		// I'm dealing with Neo4jNodes until the very end because it's easier to
		// check whether two Invocations are the same node (just check URL)
		//
		// This is also why I don't simply call the simple getPaths(Node,Node)
		// on every pair in the foreach loop
		ArrayList<Invocation> results = new ArrayList<Invocation>();

		ArrayList<RelationshipSpec> relationships = new ArrayList<RelationshipSpec>();
		relationships.add(new RelationshipSpec(Neo4jBuilder.GEN_BY_REL, "out"));
		relationships.add(new RelationshipSpec(Neo4jBuilder.USED_REL, "out"));
		relationships.add(new RelationshipSpec(Neo4jBuilder.INIT_INPUT_REL,
				"out"));

		for (Entry<Node, ArrayList<Node>> nodePair : nodePairs.entrySet()) {
			ArrayList<Neo4jNode> node1list = Neo4jNode.getNodes(nodePair
					.getKey().getNodeTp(), "id", nodePair.getKey().getNodeId());
			if (node1list == null)
				return null;
			if (node1list.size() < 1)
				return null;

			for (Node endNode : nodePair.getValue()) {
				ArrayList<Neo4jNode> node2list = Neo4jNode.getNodes(
						endNode.getNodeTp(), "id", endNode.getNodeId());
				if (node1list == null || node2list == null)
					return null;
				if (node1list.size() < 1 || node2list.size() < 1)
					return null;

				// go through each pairing of start and end nodes
				for (Neo4jNode node1 : node1list) {
					for (Neo4jNode node2 : node2list) {
						PathSpec spec = new PathSpec();
						spec.setAlgorithm(PathSpec.ALL_PATHS); // find all paths
																// between the
																// nodes
						spec.setMaxDepth(MAX_DEPTH);
						spec.setToNode(node2);
						spec.setRelationships(relationships);
						// find the paths
						ArrayList<PathResult> paths = node1.findPaths(spec);

						for (PathResult path : paths) {
							// first make sure the path contains all the through
							// nodes
							if (throughNodes != null) {
								boolean containsThroughNodes = true;
								for (Node node : throughNodes) {
									boolean containsNode = false;
									for (Neo4jNode neoNode : path.getNodes()) {
										if (compare(node, neoNode)) {
											containsNode = true;
											break;
										}
									}
									if (!containsNode) {
										containsThroughNodes = false;
										break;
									}
								}
								// if it doesn't contain all the through nodes
								// skip this path
								if (!containsThroughNodes)
									continue;
							}
							int pathLength = path.getNodes().size();
							for (int i = 0; i < pathLength; i++) {
								Neo4jNode neoNode = path.getNodes().get(i);
								if (neoNode.getProperty("type").equals(
										Neo4jBuilder.INVOC_TYP)) {
									// first check if it is in the correct
									// run, then add if it is
									if (runId == null
											|| neoNode.getProperty("run")
													.equals(runId)) {
										addInvoc(
												results,
												neoNode,
												(i > 0 ? path.getNodes().get(
														i - 1) : null),
												((i < (pathLength - 1) ? path
														.getNodes().get(i + 1)
														: null)));
									}
								}
							}
						}
					}
				}
			}
		}

		return results;
	}

	/**
	 * Compares a Node and a Neo4jNode. uses node type and node id for the
	 * comparison
	 * 
	 * @param node
	 *            the Node object to compare
	 * @param neoNode
	 *            the Neo4jNode to compare
	 * @return true if type and id are equal, false otherwise
	 */
	private static boolean compare(Node node, Neo4jNode neoNode) {
		return neoNode.getProperty("type").equals(node.getNodeTp())
				&& neoNode.getProperty("id").equals(node.getNodeId());
	}

	/**
	 * Gets the Neo4jNode representing the run with the given id
	 * 
	 * @param id
	 *            id of run node to return
	 * @return run node retrieved from database
	 */
	private static Neo4jNode getRunNode(String id) {
		return Neo4jNode.getNode("run", "id", id);
	}

	/**
	 * Adds and invocation to a list if it is not already there. also sets the
	 * given inputs and outputs on the invocation
	 * 
	 * @param invocs
	 *            list of invocations to add to
	 * @param invocNode
	 *            invocation to add to list
	 * @param output
	 *            output data artifact node to set on invocation. null to not
	 *            set
	 * @param input
	 *            input data artifact node to set on invocation. null to not set
	 */
	private static void addInvoc(ArrayList<Invocation> invocs,
			Neo4jNode invocNode, Neo4jNode output, Neo4jNode input) {
		Invocation invoc = getInvocationNoData(invocNode);
		int index = invocs.indexOf(invoc);
		if (index == -1) {
			invoc.setInputData(new Hashtable<String, DataArtifact>());
			invoc.setOutputData(new Hashtable<String, DataArtifact>());
			invocs.add(invoc);
			index = invocs.size() - 1;
		}

		if (output != null) {
			DataArtifact prevData = getDataArtifact(output);
			if (!invocs.get(index).getOutputData()
					.containsKey(prevData.getDataArtifactId()))
				invocs.get(index).getOutputData()
						.put(prevData.getDataArtifactId(), prevData);
		}
		if (input != null) {
			DataArtifact nextData = getDataArtifact(input);
			if (!invocs.get(index).getInputData()
					.containsKey(nextData.getDataArtifactId()))
				invocs.get(index).getInputData()
						.put(nextData.getDataArtifactId(), nextData);
		}
	}

}
